import java.util.Arrays;

/**
 * 628. 三个数的最大乘积
 * https://leetcode-cn.com/problems/maximum-product-of-three-numbers/
 */
public class Solutions_628 {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};  // output: 6
//        int[] nums = {1, 2, 3, 4};  // output: 24
//        int[] nums = {-1, -2, -3};  // output: -6

        int result = maximumProduct(nums);
        System.out.println(result);
    }

    /**
     * 解法二：线性遍历（2ms）
     * 找出最大的三个数，与最小的两个数
     */
    public static int maximumProduct(int[] nums) {
        int max1, max2, max3;
        max1 = max2 = max3 = Integer.MIN_VALUE;

        int min1, min2;
        min1 = min2 = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num > max1) {
                // 大于第一大的
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                // 大于第二大的
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                // 大于第三大的
                max3 = num;
            }

            if (num < min1) {
                // 小于第一小的
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                // 小于第二小的
                min2 = num;
            }
        }
        int product1 = max1 * max2 * max3;
        int product2 = max1 * min1 * min2;
        return Math.max(product1, product2);
    }

    /**
     * 解法一：直接排序（12ms）
     * 两种可能
     * 1. 最大的三个数相乘
     * 2. 最大的一个数，最小的两个数相乘
     */
    public static int maximumProduct2(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        int product1 = nums[0] * nums[1] * nums[len - 1];
        int product2 = nums[len - 1] * nums[len - 2] * nums[len - 3];
        return Math.max(product1, product2);
    }
}
